(1) Field of the Invention
The present invention relates to a method and apparatus for assigning a temporary label to each connected area in an image. The present invention also relates to a method and apparatus for converting a temporary label assigned to each connected area in an image, to a true label so that one true label is assigned to each connected area, and different true labels are assigned to connected areas which are not connected to each other. Generally, any area in an image is constituted by at least one pixel, and the processing must be performed on pixels when the image is processed by a computer. When the above assignment of a label to each connected area is performed by a computer, the operation of assigning the label to each connected area is actually the assignment of the label to each of the at least one pixel in each connected area. Conventionally, the assignment of the label to each pixel in an image is performed pixel by pixel in the manner of a raster scan. Namely, throughout this specification, it is assumed that scanning is performed row by row and in a predetermined direction in each row.
Generally, an image may contain one or more connected areas each of which is constituted by a group of pixels which are in contact with each other (in any of the vertical, horizontal, and diagonal directions) and having a value or values different from the value of the pixels in the background area. Note that, through the specification, the expression, "a pixel value" or "a value of pixel" means a value indicating brightness of the pixel, or a set of values indicating brightness of three primary colors.
An example of an image is shown in FIG. 1. When processing such an image, it is often required to assign a label to each of the above connected areas as indicated in FIG. 1. In FIG. 1, labels A1, A2, and A3 are assigned to the connected areas, respectively. Throughout this specification, pixels in an image which do not belong to the background are treated in the same way regardless of the values of the respective pixels as long as the pixel values are different from the pixel value of the background, since the inventors' interest is directed only to the assignment of a label to each connected area. Namely, when the image to be processed is a multi-valued image such as a color image or an image with gradation, the pixels in the respective connected areas may have various values other than the pixel value of the background, the label assignment within the scope of the present invention can be carried out regardless of the pixel values within the respective connected areas as long as the pixel values are different from the pixel value of the background. Therefore, in this specification, all the explanations basically concern binary images in which it is assumed that the pixel value in the background is "0", and the pixel values in the respective connected areas are "1". In the embodiments of the present invention, the pixel values in the respective connected areas may be various values other than the pixel value of the background. However, the techniques for a binary image described in the specification can be applied to any multi-valued image for the above-explained reason.
(2) Description of the Related Art
FIG. 2 is a diagram illustrating an example binary pixel image containing a white background area and two connected areas each of which is constituted by a group of pixels (where each pixel in the respective connected areas is indicated by a black square in FIG. 2). In the raster-scan type labelling, the label assignment is carried out in two steps. First, a temporary label is assigned to the respective pixels in the image by raster-scanning the image by use of a window (or mask), and then the temporary labels are converted to true labels by raster-scanning the image again, where the true label assignment is performed so that only one true label is assigned to each connected area and different true labels are assigned to connected areas which are not connected to each other. Conventionally, the window (or mask) as indicated in FIG. 3 is used in the temporary label assignment. As indicated in FIG. 3, the conventional window contains only one pixel of interest (the pixel to which a temporary label is to be newly assigned when the window is located at each position during the raster scanning), and the window (or mask) as indicated in FIG. 3 is moved one pixel by one pixel along the paths of the raster scan so that the respective pixels in the image are scanned as the pixel of interest in the window. Namely, the raster scan is carried out concerning the pixels of interest one pixel by one pixel.
In the above operation of temporary label assignment, when the pixel of interest is determined to be connected to (in contact with) another pixel to which the temporary label has already been assigned, the same temporary label is assigned to the pixel of interest. When the pixel of interest is determined not to be connected to (in contact with) a pixel to which the temporary label has already been assigned, a new temporary label is assigned to the pixel of interest. Thus, a temporarily-labelled image, as indicated in FIG. 4, is obtained.
In addition, during the operation of temporary label assignment, connection relationships between groups of pixels (areas constituted by pixels) to which groups (areas) respectively different temporary labels are assigned, are determined as indicated in FIG. 5. FIG. 5 indicates that a temporarily-labelled area in which the temporary label "1" is assigned to respective pixels in the area, is connected to a temporarily-labelled area in which the temporary label "2" is assigned to respective pixels in the area, to a temporarily-labelled area in which the temporary label "3" is assigned to respective pixels in the area, and to a temporarily-labelled area in which the temporary label "6" is assigned to respective pixels in the area.
The connection relationship is stored in the form of a label connection table (or connection relationship table), for example, as indicated in FIG. 6. In the table of FIG. 6, one entry is provided for each temporary label, and numbers, "0", "1", "2", . . . are used as the temporary labels. In the table of FIG. 6, the number "0" is assigned as the temporary label to respective pixels in the background area. When a temporarily-labelled area in which a temporary label is assigned to respective pixels in the area, is not connected to any other temporarily-labelled area in which a first temporary label with a smaller number is assigned, "0" is written in the entry for the temporary label. When a temporarily-labelled area, in which a number is assigned as the temporary label to respective pixels in the area, is connected to any other temporarily-labelled area in which a second temporary label with a smaller number is assigned, the smaller number is written in the entry for the above first temporary label "0". Thus, the table of FIG. 6 indicates that: the temporarily-labelled area in which the number "1" is assigned as the temporary label to respective pixels in the area, is not connected to any other temporarily-labelled area in which a number smaller than the number "1" is assigned as the temporary label to pixels in the area; that the temporarily-labelled area in which the number "2" as the temporary label is assigned to respective pixels in the area, is connected to the temporarily-labelled area in which the number "1" as the temporary label is assigned to respective pixels in the area; that the temporarily-labelled area in which the number "3" as the temporary label is assigned to respective pixels in the area, is connected to the temporarily-labelled area in which the number "1" as the temporary label is assigned to respective pixels in the area; that the temporarily-labelled area in which the number "4" as the temporary label is assigned to respective pixels in the area, is not connected to any other temporarily-labelled area in which a temporary label smaller than the number "4" is assigned to respective pixels in the area; that the temporarily-labelled area in which the number "5" as the temporary label is assigned to respective pixels in the area, is connected to the temporarily-labelled area in which the number "4" as the temporary label is assigned to respective pixels in the area; that the temporarily-labelled area in which the number "6" as the temporary label is assigned to respective pixels in the area, is connected to the temporarily-labelled area in which the number "1" as the temporary label is assigned to respective pixels in the area; that the temporarily-labelled area in which the number "7" as the temporary label is assigned to respective pixels in the area, is connected to the temporarily-labelled area in which the number "5" as the temporary label is assigned to respective pixels in the area; and so on.
Based on the above label connection table as FIG. 6, a (temporary-to-true) label conversion table, as indicated in FIG. 7, is generated for use in the conversion from the temporary labels to the true labels. The label conversion table of FIG. 7 has an entry for each temporary label including that for the background area, and indicates that: the temporary label "1" should be converted to the true label "1"; that the temporary label "2" should be converted to the true label "1"; that the temporary label "3" should be converted to the true label "1"; that the temporary label "4" should be converted to the true label "2"; that the temporary label "5" should be converted to the true label "2"; that the temporary label "6" should be converted to the true label "1"; that the temporary label "7" should be converted to the true label "2"; and so on. Then, based on the above label conversion table, the above raster scan for the conversion is carried out. Namely, along the paths of the raster scan, temporary labels of the respective pixels are converted to true labels pixel by pixel. After the conversion, the temporarily-labelled image is converted to a true-labelled image, for example, as indicated in FIG. 8.
However, in the above operation of the temporary label assignment, a temporary label can be assigned to only one pixel of interest while the window is located at each location, since the conventional window contains only one pixel of interest, and the window (or mask) as indicated in FIG. 3 is moved one pixel by one pixel along the paths of the raster scan. Therefore, it takes a long time to carry out the operation of the temporary label assignment.
In addition, in the above conversion from the temporary labels to the true labels, the raster scan is carried out for all of the pixels in the image subject to the label assignment. Therefore, it also takes much time to carry out the conversion from the temporary labels to the true labels.